class Solution {
    public int fib1(int n) {
        int prev = 0;
        int cur = 1;
        int next = 1;
        for(int i = 0;i<n;i++) {
            int tmp = cur ;
            cur = (prev + cur) % 1000000007 ;
            prev = tmp;
        }
        return prev ;
    }
    public int fib2(int n) {
        double cur = (1.0/Math.sqrt(5))*(Math.pow(((1.0+Math.sqrt(5))/2.0),n) -
        (Math.pow(((1.0-Math.sqrt(5))/2.0),n)));
        int ret = (int)cur % 1000000007;
        return ret ;
    }

    static final int MOD = 1000000007;

    public int fib(int n) {
       if(2>n) {
           return n;
       }
       int[][] base = {{1,1},{1,0}};
       int power = n-1;
       int[][] res = pow(base,power);
       return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        //保存如果是奇数时剃出来的那个基数
        int[][] tmp = {{1,0},{0,1}};
        while(n>0) {
            //1.若为奇数，需多乘一次 a
            //2.若power除到1，乘积后得到tmp
            if(1 == (n&1)) {
                tmp = mul(tmp,a);
            }
            n = n>>1;
            a = mul(a,a);
        }
        return tmp;
    }


    public int[][] mul(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
            }
        }
        return c;
    }


}